package leetcode_ago.LinearList;
/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 思路：1.以中间为轴【找中间节点（876）】
 * 2.反转中间节点之后的子链表2（206）
 * 3.比较2与原链表，2走到null都相同则是回文
 */
public class Num234_PalindromeLinkedList {//判断链表是否为回文链表
    public boolean isPalindrome(ListNode head) {
        //1.找到链表中间节点
        ListNode midNode=findMidNode(head);
        //2.反转中间节点之后的链表
        ListNode cur=reverse(midNode);
        //3.反转后的链表与原来链表比较
        ListNode old=head;
        while(cur!=null){

            if(cur.val!=old.val){
                return false;
            }
            cur=cur.next;
            old=old.next;
        }
        return true;
    }

    /**
     * 反转链表
     * 原地移动法：原链表的next不再指向后继而是指向前驱
     * cur:当前要处理的节点
     * prev:待处理节点的前驱节点
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode cur=head;
        ListNode prev=null;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=prev;
            //更新条件
            prev=cur;
            cur=temp;
        }
        //cur为null时，prev恰好是最后一个节点，此时这个节点也就是链表反转后的头节点
        return prev;
    }

    /**
     * 找链表中间节点
     * @param head
     * @return
     */
    private ListNode findMidNode(ListNode head) {
        //快慢指针:快指针走到结尾慢指针刚好走到中间节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}
